#ifndef AVL_TREE_H
#define AVL_TREE_H
struct AvlNode;

typedef struct AvlNode *Position;
typedef Position AvlTree;
typedef int ElementType;
struct AvlNode
{
    ElementType Element;
    AvlTree Right;
    AvlTree Left;
    int Height;
    //懒惰删除
    int Deleted;
};

AvlTree MakeEmpty(AvlTree T);
Position Find(ElementType x, AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
AvlTree Insert(ElementType x, AvlTree T);
AvlTree Delete(ElementType x, AvlTree T);
ElementType Retrieve(Position P);
void PrintTree(AvlTree T);

#endif